package demo1;

public class LeetCodeLCR173 {
    public int takeAttendance1(int[] arr) {
        //哈希表
        int n = arr.length;
        int[] hash = new int[n + 1];
        for (int i = 0; i < n; i++) hash[arr[i]]++;
        for (int i = 0; i <= n; i++) if(hash[i] == 0) return i;
        return 0;
    }

    public int takeAttendance2(int[] arr) {
        //暴力解
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != i) return i;
        }
        return arr.length;
    }

    public int takeAttendance3(int[] arr) {
        //位运算
        int sum = 0;
        for (int i = 0; i < arr.length; i++) sum ^= arr[i] ^ i;
        return sum ^ arr.length;
    }

    public int takeAttendance4(int[] arr) {
        //高斯公式
        int sum = 0, n = arr.length;
        for (int i = 0; i < n; i++) sum += i - arr[i];
        return sum + n;
    }

    public int takeAttendance(int[] arr) {
        //二分查找
        int n = arr.length, left = 0, right = n - 1;
        if(arr[right] == right) return n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}
